Codeforces Round 544(Div. 3)

Diposting di | Edited on

传送门

A.Middle of the Contest （签到）

题意

求两个时间的中间时刻

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e8+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;

int main()
{
    /*std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);*/
    int h1,h2,m1,m2;
    string s;
    cin>>s;
    h1=(s[0]-'0')*10+s[1]-'0';
    m1=(s[3]-'0')*10+s[4]-'0';
    cin>>s;
    h2=(s[0]-'0')*10+s[1]-'0';
    m2=(s[3]-'0')*10+s[4]-'0';
    int h3=h1*60+m1;
    int m3=h2*60+m2;
    int num=(h3+m3)/2;
    printf("%02d:%02d\n",num/60,num%60);
    return 0;
}

B - Preparation for International Women’s Day (水)

题意

求有多少个数可以组合成K的倍数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e8+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
int low[150];
int high[150];
int flag[150];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        high[a%k]++;
    }
    int ans=high[0]/2;
    for(int i=1;i<k/2;i++)ans+=min(high[i],high[k-i]);
    if(k%2==0)ans+=high[k/2]/2;
    else ans+=min(high[k/2],high[k/2+1]);
    cout<<ans*2<<endl;
    return 0;
}

C - Balanced Team (单调队列)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e8+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
int a[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,k;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    deque<int>dq;
    sort(a+1,a+1+n);
    int ans=0;
    for(int i=1;i<=n;i++){
        dq.push_back(a[i]);
        while(!dq.empty()&&dq.front()+5<dq.back())dq.pop_front();
        ans=max(ans,(int)dq.size());
    }
    cout<<ans<<endl;
    return 0;
}

D - Zero Quantity Maximization (map)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e8+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
ll a[maxn],b[maxn];
map<pair<ll,ll>,int>mp;
int ans=0;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    int zero=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int j=1;j<=n;j++)cin>>b[j];
    for(int i=1;i<=n;i++){
        if(a[i]==0&&b[i]==0){
            zero++;
            continue;
        }
        if(a[i]==0)continue;
        ll q=__gcd(abs(a[i]),abs(b[i]));
        a[i]/=q;
        b[i]/=q;
        if(a[i]<0)b[i]=-b[i],a[i]=-a[i];
        mp[{a[i],b[i]}]++;
        ans=max(ans,mp[{a[i],b[i]}]);
    }
    cout<<ans+zero;
    return 0;
}

E - K Balanced Teams (DP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e8+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
int dp[5500][5500],a[maxn],b[maxn];
deque<int>dq;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,k,ans=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        dq.push_back(a[i]);
        while(!dq.empty()&&dq.front()+5<dq.back())dq.pop_front();
        b[i]=dq.size();
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j]);
            dp[i][j]=max(dp[i][j],dp[i-b[i]][j-1]+b[i]);
            ans=max(dp[i][j],ans);
        }
    }
    cout<<ans;
    return 0;
}

F1 - Spanning Tree with Maximum Degree (MST)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e8+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
vector<int>G[maxn];
int a[maxn],b[maxn],fa[maxn],d[maxn];
int find(int x){
    return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
void fix(int u,int v){
    int fu=find(u);
    int fv=find(v);
    if(fv==fu)return;
    fa[fu]=fv;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m,mx=0,rt;
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
        d[a[i]]++;d[b[i]]++;
        if(d[a[i]]>mx)mx=d[a[i]],rt=a[i];
        if(d[b[i]]>mx)mx=d[b[i]],rt=b[i];
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    for(int i=0;i<G[rt].size();i++){
        cout<<rt<<" "<<G[rt][i]<<endl;
        fix(rt,G[rt][i]);
    }
    for(int i=1;i<=m;i++){
        int aa=find(a[i]),bb=find(b[i]);
        if(aa==bb)continue;
        cout<<a[i]<<" "<<b[i]<<endl;
        fix(a[i],b[i]);
    }
    return 0;
}

F2 - Spanning Tree with One Fixed Degree (构造)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e8+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
vector<int>G[maxn];
int a[maxn],b[maxn],fa[maxn],d[maxn];
int find(int x){
    return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
void fix(int u,int v){
    int fu=find(u);
    int fv=find(v);
    if(fv==fu)return;
    fa[fu]=fv;
}
bool flag[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)fa[i]=i;
    int cnt=0;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
        if(a[i]!=1&&b[i]!=1&&(find(a[i])!=find(b[i])))fix(a[i],b[i]),cnt++;
    }
    for(int i=1;i<=m;i++){
        if(a[i]==1||b[i]==1){
            int aa=find(a[i]);
            int bb=find(b[i]);
            if((aa!=bb)&&k){
                fix(a[i],b[i]);
                k--;cnt++;
                flag[i]=1;
            }
        }
    }
    for(int i=1;i<=m;i++){
        if(a[i]==1||b[i]==1){
            int aa=find(a[i]);
            int bb=find(b[i]);
            if(aa==bb&&flag[i]==0&&k){
                k--;
                flag[i]=1;
            }
        }
    }
    if(k||cnt!=n-1)cout<<"NO"<<endl,exit(0);
    cout<<"YES"<<endl;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        if(flag[i]){
            fix(a[i],b[i]);
            cout<<a[i]<<" "<<b[i]<<endl;
        }
    }
    for(int i=1;i<=m;i++){
        if(a[i]!=1&&b[i]!=1){
            if(find(a[i])!=find(b[i])){
                fix(a[i],b[i]);
                cout<<a[i]<<" "<<b[i]<<endl;
            }
        }
    }

    return 0;
}